package pers.tz.题目.leetcode.树;

import pers.tz.common.TreeNode;

/**
 * 平衡二叉树是一种二叉搜索树（BST），其中每个节点的两个子树的高度差不会超过1。
 * 这种类型的树是为了避免二叉搜索树退化成链表而设计的，可以在插入、删除和查找操作中保持较低的时间复杂度（一般为O(log n)）。
 * AVL树和红黑树是实现平衡二叉树的两种常见方法。
 *
 * @author irony
 * @date 2024-03-13
 */
public class leetcode_0110_平衡二叉树 {
// 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
// 如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
//
// 示例 1:
//输入：root = [3,9,20,null,null,15,7]
//输出：true
    public static void main(String[] args) {

    }

    public static boolean isBalanced(TreeNode root) {
        return process(root).balance;
    }

    private static Info process(TreeNode root) {
        if (root == null) {
            return new Info(true, 0);
        }

        Info left = process(root.left);
        Info right = process(root.right);

        boolean balance = true;
        if (!left.balance || !right.balance) {
            balance = false;
        }
        if (Math.abs(left.height - right.height) > 1) {
            balance = false;
        }

        int height = Math.max(left.height, right.height) + 1;

        return new Info(balance, height);
    }

    // 1. 左树是平衡二叉树
    // 2. 右树是平衡二叉树
    // 3. 左树的高度和右树的高度差不能超过1
    public static class Info {
        boolean balance;
        int height;

        public Info() {
        }

        public Info(boolean balance, int height) {
            this.balance = balance;
            this.height = height;
        }
    }
}
